import java.util.Arrays;

/**
 * 1005.K次取反最大化的数组和
 */
public class Exerciser10 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 这个对于取反操作，对于负数进行取反操作之后对于得到的最大和这个贡献是非常大的
        // 所以统计负数的个数为m个，进行分情况讨论
        // m > k -> 负数的个数大于取反的个数，把前k个小的值进行取反，之后剩余的值正常处理
        // m == k -> 对于负数全部取反进行相加
        // m < k -> 取反的值大于负数的值，先把负数全部取反统计和，之后看 k-m 的值是偶数还是奇数，如果为奇对于全部数据的绝对值的最小值进行取反
        // 如果为偶数就不需要进行任何的处理操作

        int n = nums.length;
        int m = 0;
        int min = Integer.MAX_VALUE; // 取最大值防止进行干扰
        // 统计负数的个数，取绝对值的最小值
        for(int x : nums) {
            if(x < 0) m++;
            min = Math.min(min,Math.abs(x));
        }

        int ret = 0;
        if (m > k) {
            // 负数的个数大于取反的个数
            // 进行排序
            Arrays.sort(nums);
            // 把前k个值进行取反
            for(int i = 0;i < k;i++) {
                ret += -nums[i];
            }
            // 剩下的值正常处理
            for(int i = k;i < n;i++) {
                ret += nums[i];
            }
        }else {
            // 负数的个数小于等于取反的个数
            // 把所有负数进行取反 计入和中 并且添加正数
            for(int x : nums) {
                ret += Math.abs(x);
            }
            // 查看 剩余的k值是奇数还是偶数
            if((k - m) % 2 != 0) {
                // 奇数，对于最小的值进行处理
                ret -= min*2;
            }
        }
        return ret;
    }
}
